package leetcode_ago.sort;

/**
 * 求数组中逆序对个数
 * 在归并过程中顺带求：归并的merge并过程就存在逆序对，统计即可
 * @author 美女
 * @date 2022/03/19 19:45
 **/

public class JZ51_arraynixudui {
    public int reversePairs(int[] nums) {
        return  reversePairsHelper(nums,0,nums.length-1);
    }
    //求数组[l...r]上逆序对的个数
    private int reversePairsHelper(int[] nums, int l, int r) {
        if(l>=r){
            //此时区间只剩一个元素，不构成逆序对
            return 0;
        }
        //将数组分别求左右区间逆序对个数
        int mid=l+((r-l)>>1);
        int left=reversePairsHelper(nums,l,mid);
        int right=reversePairsHelper(nums,mid+1,r);
        if(nums[mid]>nums[mid+1]){
            return left+right+merge(nums,l,mid,r);
        }else{
            //整个数组已经有序
            return left+right;
        }
    }
    //合并[l...mid][mid+1...r]区间的数组并在合并过程中统计数组逆序对数目
    private int merge(int[] nums, int l, int mid, int r) {
        //创建临时数组
        int[] aux=new int[r-l+1];
        int result=0;
        for (int i = 0; i < aux.length; i++) {
            aux[i]=nums[i+l];
        }
        //数组元素存到aux中
        int i=l;
        int j=mid+1;
        //k表示正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if(i>mid){
                //左侧合并完
                //右侧直接赋值,此时没有逆序对
                nums[k]=aux[j-l];
                j++;
            }else if(j>r){
                //右侧合并完
                //左侧值直接添加,此时没有逆序对
                nums[k]=aux[i-l];
                i++;
            }else if(aux[i-l]<=aux[j-l]){
                nums[k]=aux[i-l];
                i++;
            }else{
                //左侧值大于右侧，存在逆序对
                //此时逆序对个数：mid-i+1（j小于i说明小于i到mid之间所有元素【i->mid的元素有序】）
                result+=mid-i+1;
                nums[k]=aux[j-l];
                j++;
            }
        }
        return result;
    }
}


//public class JZ51_arraynixudui {
//    public int reversePairs(int[] nums) {
//        return reversePairsHelper(nums,0,nums.length-1);
//    }
//
//    /**
//     * 传入一个数组nums，就可以求出nus[l...r]上的逆序对个数
//     * @param nums
//     * @param left
//     * @param right
//     * @return 此时nums[l...r]逆序对个数
//     */
//    private int reversePairsHelper(int[] nums, int left, int right) {
//        if(left>=right){
//            //区间只剩一个元素了，不构成逆序对
//            return 0;
//        }
//        int mid=left+((right-left)>>1);
//        //先递归求出左区间逆序对
//        int leftPairs=reversePairsHelper(nums,left,mid);
//        //再求出右区间逆序个数
//        int rightPairs=reversePairsHelper(nums,mid+1,right);
//        //当左右区间没有排序好，进入merge求其中的逆序对个数，否则左右已排序好merge中就没有逆序对，直接返回leftPairs+rightPairs
//        if(nums[mid]>nums[mid+1]){
//            //左区间最后的元素>右区间起始元素，未排序好
//            return merge(nums,left,mid,right)+leftPairs+rightPairs;
//        }
//        //此时左右区间有序，整个集合也有序
//        return leftPairs+rightPairs;
//    }
//
//    /**
//     * 合并nums的两个有序区间[l...mid][mid+1...r]
//     * @param nums
//     * @param left
//     * @param mid
//     * @param right
//     * @return 合并过程中逆序对的个数
//     */
//    private int merge(int[] nums, int left, int mid, int right) {
//        int[] aux=new int[right-left+1];
//        //合并过程中产生的逆序对个数
//        int res=0;
//        for (int i = 0; i < aux.length; i++) {
//            aux[i]=nums[i+left];//nums有left个单位的偏移量
//        }
//        //左右两个小数组开始位置的索引
//        int i=left;
//        int j=mid+1;
//        //k表示当前正在合并的原数组的索引下标
//        for (int k = left; k <=right; k++) {
//            if(i>mid){//左侧合并完了，放入右区间元素
//                nums[k]=aux[j-left];
//                j++;
//            }else if(j>right){//右侧小数组遍历完了，左侧放入
//                nums[k]=aux[i-left];
//                i++;
//            }else if(aux[i-left]<=aux[j-left]){
//                //不构成逆序对，直接左侧元素覆盖nums[k]
//                nums[k]=aux[i-left];
//                i++;
//            }else{
//                //右区间元素>左区间元素，构成逆序对
//                //此时逆序对个数：mid-i+1（j小于i说明小于i到mid之间所有元素【i->mid的元素有序】）
//                res+=(mid-i)+1;
//                //右边小于左边，右边元素往nums[k]上覆盖
//                nums[k]=aux[j-left];
//                j++;
//            }
//        }
//        return res;
//    }
//
//
//}
